Buffers and caches are often used in computing systems to temporarily hold items that are frequently accessed or whose access time may otherwise inhibit performance. Since buffers and caches have limited size, techniques used to efficiently utilize their limited space strongly influence their performance. One type of buffer is a circular buffer implemented in software. A circular buffer is a list of items linked in a circular fashion. Each item in the list is linked to a previous item and a next item, where the first item in the list is the next item with respect to the last item on the list, i.e., the items are linked in a circle. Two algorithms are necessary to operate such a buffer: first, an algorithm to select an item to delete when a new item is to be inserted into a full buffer; second, an algorithm to select a location for the new item. A location from which an item is deleted to make space for a new item and a location to which the new item is inserted may not be the same location. This happens more often in software implemented buffers than those implemented in hardware. The logic that selects these locations is embodied in a replacement algorithm which has a profound effect on the performance of a buffer under various workloads. The performance of a buffer is usually measured by its hit rate, the fraction of accesses to a buffer that find an accessed item in the buffer. The performance of a given replacement algorithm will vary under different circumstances and depends strongly on the access pattern of a program using a buffer.
A common replacement algorithm used with a buffer or a cache is least recently used or LRU. When a new item must be added to a full buffer, the LRU algorithm evicts an item from the buffer or a section of the buffer that has not been accessed for the longest period of time compared to that of other items under consideration and the new item replaces the evicted item. Unfortunately, in some buffer configurations and for large buffers, the logic necessary to keep track of a LRU item and the next LRU item, etc. can be significant.